Classification Trees

• Max Kuhn. Chapter 14. Section 14.1

Classification is a process of finding the decision boundary that best separate two classes

• Decision Tree for classification is Classification Tree
• Decision Tree for Regression is Regression Tree

Link

• In two dimension, classification Tree's decision boundary is a collection of horiontal and vertical line

• The tree starts by a vertical or horizontal line that best seperate the data
• Question: Find a vertical line that best seperate red and green.

• Question: Which is the best split?

• It looks like Split 1 and 3 are better than Split 2 since it misclassifies less
• Which is the better split between Split 1 and Split 3?
• We need to find a way to measure how good a split is

• The impurity of a node (a node = a subset of the data or the original data) measure how uncertain the node is.
  
• For example, node A with 50% reds and 50% greens would be more uncertained than node B with 90% reds and 10% greens. Thus, node A has greater impurity than node B.
• More uncertained \( = \) Greater impurity

• A split that gains more impurity is the better split!

\[ IG = I_{parent} - \frac{N_{left}}{N}I_{left}-\frac{N_{right}}{N}I_{right} \]

• IG is Impurity Gain of the split
• \( N_{left} \) and \( N_{right} \) are the number of points in the left child node and right child node, respectively.
• \( N_{left}+N_{right}=N \)

• Impurity can be measured by: classification error, Gini Index, and Entropy.

• Let \( p_0 \) and \( p_1 \) be the proportion of class 0 and class 1 in a node.
  

\[ \begin{aligned} {\text{By Classification Error: }} I &= min\{p_0, p_1\} \\ {\text{By Gini Index: }} I&= 1 - p_0^2-p_1^2 \\ {\text{By Entropy: }} I &= -p_0 \log_2(p_0)-p_1\log_2(p_1) \end{aligned} \]

• Let's calculate the impurity gain of the three splits to decide which split is the best

• Let green and red be class 0 and class 1, respectively.

For Split 1: \( N = 5, N_{left} =1, N_{right} = 4 \)

• Node parent, A: \( p_0 = \frac{2}{5}, p_1 = \frac{3}{5} \). Thus, \( I_{A} = \text{min}(\frac{2}{5}, \frac{3}{5}) = \frac{2}{5} \)

• Node child left, L: \( p_0 = \frac{0}{1} = 0, p_1 = \frac{1}{1} = 1 \). Thus, \( I_{L} = \text{min}(0, 1) = 0 \)

• Node child right, R: \( p_0 = \frac{3}{4}, p_1 = \frac{1}{4} \). Thus, \( I_{R} = \text{min}(\frac{3}{4}, \frac{1}{4}) = \frac{1}{4} \)

• Impurity Gain of Split 1:

\[ IG = \frac{2}{5} - \frac{1}{5} \cdot 0-\frac{4}{5} \cdot \frac{1}{4} = 0.2 \]

For Split 2: \( N = 5, N_{left} =2, N_{right} = 3 \)

• Node parent, A: \( p_0 = \frac{2}{5}, p_1 = \frac{3}{5} \). Thus, \( I_{A} = \text{min}(\frac{2}{5}, \frac{3}{5}) = \frac{2}{5} \)

• Node child left, L: \( p_0 = \frac{1}{2}, p_1 = \frac{1}{2} \). Thus, \( I_{L} = \frac{1}{2} \)

• Node child right, R: \( p_0 = \frac{2}{3}, p_1 = \frac{1}{3} \). Thus, \( I_{R} = \text{min}(\frac{2}{3}, \frac{1}{3}) = \frac{1}{3} \)

• Impurity Gain of Split 2:

\[ IG = \frac{2}{5} - \frac{2}{5} \cdot \frac{1}{2}-\frac{3}{5} \cdot \frac{1}{3} = 0 \]

For Split 3: \( N = 5, N_{left} =3, N_{right} = 2 \)

• Node parent, A: \( p_0 = \frac{2}{5}, p_1 = \frac{3}{5} \). Thus, \( I_{A} = \text{min}(\frac{2}{5}, \frac{3}{5}) = \frac{2}{5} \)

• Node child left, L: \( p_0 = \frac{1}{3}, p_1 = \frac{2}{3} \). Thus, \( I_{A} = \text{min}(\frac{1}{3}, \frac{2}{3}) = \frac{1}{3} \)

• Node child right, R: \( p_0 = \frac{2}{2}, p_1 = \frac{0}{2} \). Thus, \( I_{R} = \text{min}(1,0) = 0 \)

• Impurity Gain of Split 3:

\[ IG = \frac{2}{5} - \frac{3}{5} \cdot \frac{1}{3}-\frac{2}{5} \cdot 0 = 0.2 \]

For Split 1: \( N = 5, N_{left} =1, N_{right} = 4 \)

• Node parent, A: \( p_0 = \frac{2}{5}, p_1 = \frac{3}{5} \). Thus, \( I_{A} = 1 - (\frac{2}{5})^2-(\frac{3}{5})^2 = 0.48 \)

• Node child left, L: \( p_0 = \frac{0}{1} = 0, p_1 = \frac{1}{1} = 1 \). Thus, \[ I_{L} = 1 -0^2-1^2 = 0 \]

• Node child right, R: \( p_0 = \frac{3}{4}, p_1 = \frac{1}{4} \). Thus, \[ I_{R} = 1-(\frac{3}{4})^2-(\frac{1}{4})^2 = 0.375 \]

• Impurity Gain of Split 1:

\[ IG = 0.48 - \frac{1}{5} \cdot 0-\frac{4}{5} \cdot 0.375 = 0.18 \]

For Split 2: \( N = 5, N_{left} =2, N_{right} = 3 \)

• Node parent, A: \( p_0 = \frac{2}{5}, p_1 = \frac{3}{5} \). Thus, \( I_{A} = 1-(\frac{2}{5})^2- (\frac{3}{5})^2 = 0.48 \)

• Node child left, L: \( p_0 = \frac{1}{2}, p_1 = \frac{1}{2} \). Thus, \( I_{L} = 1- (\frac{1}{2})^2-(\frac{1}{2})^2=0.5 \)

• Node child right, R: \( p_0 = \frac{2}{3}, p_1 = \frac{1}{3} \). Thus, \( I_{R} = 1-(\frac{2}{3})^2 -(\frac{1}{3})^2 = 0.44 \)

• Impurity Gain of Split 2:

\[ IG = 0.48 - \frac{2}{5} \cdot \frac{1}{2}-\frac{3}{5} \cdot 0.44 = 0.016 \]

For Split 3: \( N = 5, N_{left} =3, N_{right} = 2 \)

• Node parent, A: \( I_{A} = 0.48 \)

• Node child left, L: \( p_0 = \frac{1}{3}, p_1 = \frac{2}{3} \). Thus, \( I_{A} = 1-(\frac{1}{3})^2 -(\frac{2}{3})^2 = 0.44 \)

• Node child right, R: \( p_0 = \frac{2}{2}, p_1 = \frac{0}{2} \). Thus, \( I_{R} = 1-0^2-1^2 = 0 \)

• Impurity Gain of Split 3:

\[ IG = 0.48 - \frac{3}{5} \cdot 0.44 - \frac{2}{5} \cdot 0 = 0.216 \]

For Split 1: \( N = 5, N_{left} =1, N_{right} = 4 \)

• Node parent, A: \( p_0 = \frac{2}{5}, p_1 = \frac{3}{5} \). Thus, \( I_{A} = - log_2(\frac{2}{5})-log_2(\frac{3}{5}) = 0.971 \)

• Node child left, L: \( p_0 = \frac{0}{1} = 0, p_1 = \frac{1}{1} = 1 \). Thus, \( I_{L} = 0 \)

• Node child right, R: \( p_0 = \frac{3}{4}, p_1 = \frac{1}{4} \). Thus, \[ I_{R} = -\frac{3}{4} \cdot log_2(\frac{3}{4})-\frac{1}{4} \cdot log_2(\frac{1}{4}) = 0.811 \]

• Impurity Gain of Split 1:

\[ IG = 0.971 - \frac{1}{5} \cdot 0-\frac{4}{5} \cdot 0.811 = 0.322 \]

For Split 2: \( N = 5, N_{left} =2, N_{right} = 3 \)

• Node parent, A: \( p_0 = \frac{2}{5}, p_1 = \frac{3}{5} \). Thus, \( I_{A} = 0.971 \)

• Node child left, L: \( p_0 = \frac{1}{2}, p_1 = \frac{1}{2} \). Thus, \( I_{L} = - log_1(\frac{1}{2})-log_2(\frac{1}{2})=1 \)

• Node child right, R: \( p_0 = \frac{2}{3}, p_1 = \frac{1}{3} \). Thus, \( I_{R} = -\frac{2}{3} \cdot log_2(\frac{2}{3}) -\frac{1}{3} \cdot log_2(\frac{1}{3}) = 0.918 \)

• Impurity Gain of Split 2:

\[ IG = 0.971 - \frac{2}{5} \cdot 1-\frac{3}{5} \cdot 0.918 = 0.02 \]

For Split 3: \( N = 5, N_{left} =3, N_{right} = 2 \)

• Node parent, A: \( I_{A} = 0.971 \)

• Node child left, L: \( p_0 = \frac{1}{3}, p_1 = \frac{2}{3} \). Thus, \( I_{A} = -log_2(\frac{1}{3}) -log_2(\frac{2}{3}) = 0.918 \)

• Node child right, R: \( p_0 = \frac{2}{2}, p_1 = \frac{0}{2} \). Thus, \( I_{R} = 0 \)

• Impurity Gain of Split 3:

\[ IG = 0.971 - \frac{3}{5} \cdot 0.918 - \frac{2}{5} \cdot 0 = 0.42 \]

• Besides impurity gain, one can use the Chi-square, \( \chi^2 \), test of independence to decide the best split.

• Let \( X \) and \( Y \) be two categorical variables.

• We want to test if \( X \) and \( Y \) are independent/associated

  • \( H_0 \): \( X \) and \( Y \) are independent
  • \( H_{\alpha}: \) \( X \) and \( Y \) are dependent

• Test statistic:

\[ \sum\frac{(e_i-o_i)^2}{e_i} \sim \chi^2 \text{ distribution with degree of freedom} (n-1)(m-1) \]

• In our context, the greater the \( \chi^2 \) value, the smaller the \( p-value \)
• The smaller the \( p-value \), the more dependent the two variables are. Thus the better the split is.
• Therefore, we look for the split with the greatest \( \chi^2 \) value.

• We will calculate the \( \chi^2 \) values of the three splits.
  
• The best split is the split with the greatest \( \chi^2 \) value.

• The quality of the split can be measured by Logworth
• Formula: \[ logworth = -log(p\text{_}value) \]
• The greater the logworth, the better the split

• After the first split, the data are divided into to subsets.
• The splitting process is repeated for each subset.
• The process ends when a stopping criteria is satisfied

• Minimum Leaf Size: The minimum of observations in the leaves
• Maximum Number of Leaves
• Maximum Depth
• Others

• Step 1: Calculate the impurity gain or \( p-value \) of all possible splits at all variables
• Step 2: Select the split that give the maximum impurity gain or lowest \( p-value \) to split the data into two subdata \( D_1 \) and \( D_2 \)
• Repeat Step 1 and Step 2 to both \( D_1 \) and \( D_2 \).
• Until a stopping criteria is satisfied

• A complexity of a tree can be measured by the number of leaves the tree has
• The more leaves a tree has, the more complex the tree is.
• A complex tree may be overfitted, i.e. having low training error but high testing error.

• For any given data, one can construct a tree that achives 0 misclassification on training data
• After growing the tree one needs to prune it to avoid overfittted

• The tree with maximum number of leaves is called the maximal tree (still satisfied the stopping rule)
• From the maximal tree, leaves are cut down, one by one, to obatined all possible subtrees
• The subtree with lowest error on validation data, is the optimal tree